package 剑指offer;

import java.util.ArrayList;
import java.util.Scanner;
import java.util.Vector;

import org.w3c.dom.ls.LSException;

/** 

* @author ：soulstones
* @version ：2019年9月30日 下午9:50:14 
* @Description：
* 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，
* 则最小的4个数字是1,2,3,4,。

*/
public class A29最小的K个数 {

	//最简单的冒泡排序思想
	//在最外层循环k次，只需要找出k个就好了
	
	//o(K N) 最坏的是k趋近n,变为了o(^2)
public static  ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list  = new ArrayList<Integer>();
        
        if (k>input.length) {
			return list;
		}
        
        for (int i = 0; i <k; i++) {
			for (int j = 0; j < input.length-i-1; j++) {
				if (input[j]<input[j+1]) {
					int temp=input[j];                 //在这里是把最小值放到数组尾部
					input[j]=input[j+1];
					input[j+1]=temp;
				}
			}
			list.add(input[input.length-i-1]);          //每次循环结束后，在数组尾部的都是当前数组中的最小值了
		}
        return list;
    }

//快排思想
/*
利用快速排序中的获取分割（中轴）点位置函数getPartitiion。
基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，
比第k个数字大的所有数字都位于数组的右边。调整之后，位于数组左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。O(N)
 */

public static ArrayList<Integer> GetLeastNumbers_Solution11(int [] input, int k) {
	ArrayList<Integer> result = new ArrayList<>();
     if (input==null ||k>input.length||k<0) {
		return result;
	}
     int start=0;
     int end=input.length-1;
     int index=getPartition(input, start, end);
     
     while (index!=(k-1)) {
		if (index>(k-1)) {
			end=index-1;
			index=getPartition(input, start, end);
		}else {
			start=index+1;
			index=getPartition(input, start, end);
		}
	}
     for (int i = 0; i < k; ++i) {
		result.add(input[i]);
	}
     return result;
}

public static void swap(int first,int sec) {
	int temp=first;
	first=sec;
	sec=temp;
}

public static int getPartition(int [] input,int start,int end) {
	if (input.length==0|| start>end) 
		return Integer.MIN_VALUE;
	int temp=input[end];
	int j=start-1;
	for(int i=start;i<end;++i) {
		if (input[i]<=temp) {
			++j;
			if (i!=j) 
				swap(input[i], input[j]);
		}
	}
	swap(input[j+1], input[end]);
	return (j+1);
}




//利用堆排序（大根堆，小根堆）利用堆排序，O(N logK)，适合处理海量数据

	public static ArrayList<Integer> GetLeastNumbers_Solution22(int[] input, int k) {
		ArrayList<Integer> list = new ArrayList<>();
		if (input == null || input.length <= 0 || input.length < k) {
			return list;
		}
		// 构建最大堆
		for (int len = k / 2 - 1; len > 0; len--) {
			adjustMaxHeap(input, len, k - 1);
		}

		// 从第k个元素开始分别与最大堆的最大值做比较，如果比最大值小，则替换并调整堆。
		// 最终堆里的就是最小的K个数。
		int tmp;
		for (int i = k; i < input.length; i++) {
			if (input[i] < input[0]) {
				tmp = input[0];
				input[0] = input[i];
				input[i] = tmp;
				adjustMaxHeap(input, 0, k - 1);
			}
		}
		for (int j = 0; j < k; j++) {
			list.add(input[j]);
		}
		return list;
	}
	
public static void adjustMaxHeap(int [] input,int pos,int length) {
	int temp,child;
	
	for(temp=input[pos];2*pos+1<=length;pos=child) {
		child=2*pos+1;
		if (child<length&&input[child]<input[child+1]) {
			child++;
		}
		if (input[child]>temp) {
			input[pos]=input[child];
		}else {
			break;
		}
	}
	input[pos]=temp;
}


public static void main(String[] args) {
	Scanner scanner = new Scanner(System.in);
	String s = scanner.nextLine();
	String[] ss = s.split(" ");
	int [] arr=new int [ss.length];
	for (int i = 0; i < arr.length; i++) {
		arr[i]=Integer.parseInt(ss[i]);
	}
	int k = scanner.nextInt();
	ArrayList<Integer> resultList = GetLeastNumbers_Solution(arr, k);
	System.out.println(resultList);
	ArrayList<Integer> list11= GetLeastNumbers_Solution11(arr, k);
	System.out.println(list11);
	ArrayList<Integer> list22= GetLeastNumbers_Solution22(arr, k);
	System.out.println(list22);
}
}
